package org.labuladong.动态规划算法.二维DP;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-20:49
 * @Description:
 * @version: 1.0
 */
public class LC_72minDistance {
		public int minDistance(String word1, String word2) {
			int m = word1.length(), n = word2.length();
			int[][] dp = new int[m + 1][n + 1];

			// 初始化 dp 数组
			for (int i = 0; i <= m; i++) {
				dp[i][0] = i;
			}
			for (int j = 0; j <= n; j++) {
				dp[0][j] = j;
			}

			// 动态规划
			for (int i = 1; i <= m; i++) {
				for (int j = 1; j <= n; j++) {
					if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
						dp[i][j] = dp[i - 1][j - 1];
					} else {
						dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
					}
				}
			}

			return dp[m][n];
		}

		public static void main(String[] args) {
			LC_72minDistance solution = new LC_72minDistance();
			String word1 = "horse";
			String word2 = "ros";
			System.out.println(solution.minDistance(word1, word2)); // 输出应该是 3
		}
	}